package name.huzhenbo.java.algorithm.sort;

class QuickerSorter implements Sorter {

    public int[] go(int[] input) {
        _quickSort(input, 0, input.length - 1);
        return input;
    }

    /**
     * Better then quicksort in some special case, e.g the array fill with all same items.
     * Also, the quicksort is better when under random sort.
     *
     * @param input
     * @param start
     * @param end
     */
    public void _quickSort(int[] input, int start, int end) {
        if (start >= end) {
            return;
        }
        int i = start + 1;
        int j = end;
        while (true) {
            while (i < end && input[i] < input[start]) {
                i++;
            }
            while (j > start && input[j] > input[start]) {
                j--;
            }
            if (j <= i) {
                break;
            }
            SorterUtil.swap(input, i, j);
        }
        SorterUtil.swap(input, start, j);
        _quickSort(input, start, j - 1);
        _quickSort(input, j + 1, end);
    }

}
